#include <stdio.h>

int main() {
    
    int a[1000000];
    a[0]=1;
    a[1]=2;
    for(int i =2;i<1000000;i++)
    {
         a[i]=((2*a[i-1]+a[i-2])%32767);
    }
    int n =0;
    scanf("%d",&n);

    while(n--)
    {
      int j =0;
      scanf("%d",&j);

      printf("%d\n",a[j-1]);
    }
    return 0;
}